#include"main.h"

void create_tree(BiTreeNode** root_pp, char* pre_order_seq, int num_elements) {
    static int num_element = -1;
    num_element++;
    if (pre_order_seq[num_element] != '\0' && pre_order_seq[num_element] != '#') {
        (*root_pp) = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        (*root_pp)->data = pre_order_seq[num_element];
        create_tree(&((*root_pp)->leftChild), pre_order_seq, num_elements);
        create_tree(&((*root_pp)->rightChild), pre_order_seq, num_elements);
    }
    else {
        (*root_pp) = 0;
    }
}

void pre_order_traverse(BiTreeNode* t, void visit(DataType item)) {
    if (t != 0) {
        visit(t->data);
        pre_order_traverse(t->leftChild, visit);
        pre_order_traverse(t->rightChild, visit);

    }
}

void in_order_traverse(BiTreeNode* t, void visit(DataType item)) {
    if (t != 0) {
        in_order_traverse(t->leftChild, visit);
        visit(t->data);
        in_order_traverse(t->rightChild, visit);
    }
}

void post_order_traverse(BiTreeNode* t, void visit(DataType item)) {
    if (t != 0) {
        post_order_traverse(t->leftChild, visit);
        post_order_traverse(t->rightChild, visit);
        visit(t->data);
    }
}

void visit(DataType item) {
    printf("%c\n", item);
}

BiTreeNode* search(BiTreeNode* root, DataType x) {
    if (root == 0) {
        return NULL;
    }
    else if ((root->data) == x) {
        return root;
    }
    BiTreeNode* a=search(root->leftChild, x);
    BiTreeNode* b=search(root->rightChild, x);
    if (a!=NULL){
        return a;
    }
    else {
        return b;
    }
}

void destroy(BiTreeNode** root) {
    if ((*root) != 0) {
        destroy(&((*root)->leftChild));
        destroy(&((*root)->rightChild));
        free(*root);
    }
}

int main() {
    void (*p)(DataType item) = visit;
    BiTreeNode* aa = 0;
    char po = 'A';
    create_tree(&aa, "ABC##DE#G##F###", 7);
    pre_order_traverse(aa, p);
    printf("%p", search(aa, po));
    destroy(&aa);
    return 0;
}